CODE 3. Surrounded Regions

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/09/2013-09-09-CODE 3 Surrounded Regions/
访问原文「CODE 3. Surrounded Regions」

Given a 2D board containing'X'and'O', capture all regions surrounded by'X'.
A region is captured by flipping all'O's into'X's in that surrounded region .
For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
我的代码如下：

public void solve(char[][] board) {
	if (null == board || board.length == 0) {
		return;
	}
	int m = board.length;
	int n = board[0].length;
	Queue<Integer> queue = new LinkedList<Integer>();
	for (int i = 0; i < m; i++) {
		if (board[i][0] == 'O') {
			queue.offer(i * m);
		}
		if (board[i][n - 1] == 'O') {
			queue.offer(i * m + n - 1);
		}
	}
	for (int j = 1; j < n - 1; j++) {
		if (board[0][j] == 'O') {
			queue.offer(j);
		}
		if (board[m - 1][j] == 'O') {
			queue.offer((m - 1) * m + j);
		}
	}
	while (!queue.isEmpty()) {
		int all = queue.poll();
		int x = all / m;
		int y = all % m;
		board[x][y] = 'L';
		for (int i = -1; i <= 1; i++) {
			for (int j = -1; j <= 1; j++) {
				if (x + i < 0 || x + i > m - 1 || y + j < 0
						|| y + j > n - 1 || (Math.abs(i + j) != 1)) {
					continue;
				}
				int tmpAll = (x + i) * m + y + j;
				if (board[x + i][y + j] == 'O') {
					queue.offer(tmpAll);
				}
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = board[i][j] == 'L' ? 'O' : 'X';
		}
	}
}

主要思考如下：

这道题首先使用了dfs完成，但这种方法使用了递归所以没有通过大数据集中大数据的测试；
然后使用了bfs完成，但是同样的判断语句出现了很多次，也会导致运行时间过长，具体的问题代码如下：

public void solve(char[][] board) {
	if (null == board || board.length == 0) {
		return;
	}
	int m = board.length;
	int n = board[0].length;
	Queue<Integer> queue = new LinkedList<Integer>();
	for (int i = 0; i < m; i++) {
		if (board[i][0] == 'O') {
			queue.offer(i * m);
		}
		if (board[i][n - 1] == 'O') {
			queue.offer(i * m + n - 1);
		}
	}
	for (int j = 1; j < n - 1; j++) {
		if (board[0][j] == 'O') {
			queue.offer(j);
		}
		if (board[m - 1][j] == 'O') {
			queue.offer((m - 1) * m + j);
		}
	}
	while (!queue.isEmpty()) {
		int all = queue.poll();
		int x = all / m;
		int y = all % m;
		board[x][y] = 'L';
		if (x > 0 && board[x - 1][y] == 'O') {
			queue.offer((x - 1) * m + y);
		}
		if (x < m - 1 && board[x + 1][y] == 'O') {
			queue.offer((x + 1) * m + y);
		}
		if (y > 0 && board[x][y - 1] == 'O') {
			queue.offer(x * m + y - 1);
		}
		if (y < n - 1 && board[x][y + 1] == 'O') {
			queue.offer(x * m + y + 1);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = board[i][j] == 'L' ? 'O' : 'X';
		}
	}
}